#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
using namespace std;

class Solution
{

private:
    static const int mod = 1000000007;

public:
    int candy(vector<int> &ratings)
    {
        int n = ratings.size();
        vector<int> sortedRatings(n, 0);
        for (int i = 0; i < n; i++)
        {
            sortedRatings[i] = i;
        }
        // 库函数对sortedRatings进行自定义排序
        sort(sortedRatings.begin(), sortedRatings.end(), [&](int a, int b)
             { return ratings[a] < ratings[b]; });
        vector<int> candy(n, -1);
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int index = sortedRatings[i];
            int val = 1;
            if (index > 0 && candy[index - 1] != -1 && ratings[index] > ratings[index - 1])
            {
                val = candy[index - 1] + 1;
            }
            if (index < n - 1 && candy[index + 1] != -1 && ratings[index] > ratings[index + 1])
            {
                val = std::max(val, candy[index + 1] + 1);
            }
            candy[index] = val;
            ans += val;
        }
        return ans;
    }

    int maxCandies(vector<int> &status, vector<int> &candies, vector<vector<int>> &keys, vector<vector<int>> &containedBoxes, vector<int> &initialBoxes)
    {
        int ans = 0;
        // 声明队列
        std::queue<int> q;
        vector<int> visit(status.size(), 0);

        // 将初始箱子加入队列
        for (auto &box : initialBoxes)
        {
            q.push(box);
            visit[box] = 1;
        }
        while (!q.empty())
        {
            int box = q.front();
            q.pop();
            if (status[box] == 1)
            {
                status[box] = 2;
                ans += candies[box];
                for (auto &box : containedBoxes[box])
                {
                    visit[box] = 1;
                    if (status[box] == 1 && visit[box] == 1)
                    {
                        q.push(box);
                    }
                }
                for (auto &key : keys[box])
                {
                    if (status[key] != 2)
                    {
                        status[key] = 1;
                    }
                    if (status[key] == 1 && visit[key] == 1)
                    {
                        q.push(key);
                    }
                }
            }
        }
        return ans;
    }

    string answerString(string word, int numFriends)
    {
        if (numFriends == 1)
        {
            return word;
        }
        int len = word.size();
        int start1 = 0;

        int end1 = len - numFriends;
        for (int i = 0; i < len; i++)
        {
            int start2 = i;
            int end2 = len - std::max(1, numFriends - i);
            if (!max(start1, end1, start2, end2, word))
            {
                start1 = start2;
                end1 = end2;
            }
        }
        return word.substr(start1, end1 - start1 + 1);
    }

    bool max(int x1, int y1, int x2, int y2, string &word)
    {
        while (x1 <= y1 || x2 <= y2)
        {
            if (x1 > y1)
            {
                return false;
            }
            if (x2 > y2)
            {
                return true;
            }
            if (word[x1] > word[x2])
            {
                return true;
            }
            if (word[x1] < word[x2])
            {
                return false;
            }
            x1++;
            x2++;
        }
        return true;
    }

    string smallestEquivalentString(string s1, string s2, string baseStr)
    {
        std::vector<int> dp(26, -1);
        for (int i = 0; i < 26; i++)
        {
            dp[i] = i;
        }
        int size = s1.size();
        for (int i = 0; i < size; i++)
        {
            unionA(s1[i] - 'a', s2[i] - 'a', dp);
        }
        for (int i = 0; i < baseStr.size(); i++)
        {
            baseStr[i] = find(baseStr[i] - 'a', dp) + 'a';
        }
        return baseStr;
    }

    int find(int x, std::vector<int> &dp)
    {
        if (dp[x] == x)
        {
            return x;
        }
        dp[x] = find(dp[x], dp);
        return dp[x];
    }

    void unionA(int x, int y, std::vector<int> &dp)
    {
        int a = find(x, dp);
        int b = find(y, dp);
        if (a < b)
        {
            dp[b] = a;
        }
        else
        {
            dp[a] = b;
        }
    }

    string robotWithString(string s)
    {
        int len = s.size();
        std::vector<std::queue<int>> dp(26);
        for (int i = 0; i < s.size(); i++)
        {
            dp[s[i] - 'a'].push(i);
        }
        std::string ans;
        int start = 0;
        std::stack<int> stack;
        while (!stack.empty() || start < len)
        {
            if (stack.empty())
            {
                stack.push(start);
                start++;
            }
            else
            {
                int i = stack.top();
                int val = s[i] - 'a';
                bool flag = true;
                for (int j = 0; j < val; j++)
                {
                    while (dp[j].size() > 0 && dp[j].front() < start)
                    {
                        dp[j].pop();
                    }
                    if (dp[j].size() > 0)
                    {
                        flag = false;
                        int maxStart = dp[j].front();
                        while (start <= maxStart)
                        {
                            stack.push(start);
                            start++;
                        }
                        break;
                    }
                }
                if (flag)
                {
                    ans.push_back(s[i]);
                    stack.pop();
                }
            }
        }
        return ans;
    }
};

int main()
{
    Solution solution;
    // 测试candy
    std::vector<int> ratings = {1, 2, 2};
    int ansCandy = solution.candy(ratings);
    std::cout << "candy: " << ansCandy << std::endl;

    std::unordered_map<int, int> candyMap = {{0, 1}, {1, 1}, {2, 1}};
    std::cout << candyMap[-2] << endl;

    // 测试answerString
    std::string word = "jmf";
    int numFriends = 3;
    std::string ansString = solution.answerString(word, numFriends);
    std::cout << "answerString: " << ansString << std::endl;

    // 测试robotWithString
    std::string s = "bddabddazzazzab";
    std::string ansRobot = solution.robotWithString(s);
    std::cout << "robotWithString: " << ansRobot << std::endl;
    return 0;
}
